package 数组;
import java.util.*;

/**
 * 该类用于查找数组中消失的数字。
 * 提供了多种方法：使用哈希表、哈希集合和原地交换。
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
public class findDisappearedNumbers {
    /**
     * 使用哈希集合查找消失的数字。
     * 该方法通过哈希集合记录数组中出现的数字，未出现的数字即为消失的数字。
     * @param nums 输入数组
     * @return 消失的数字列表
     */
    public List<Integer> findDisaSet(int[] nums) {
        HashSet<Integer> set = new HashSet<>(); // 哈希集合
        for(int num : nums) {
            set.add(num); // 将数组中的数字加入集合
        }
        List<Integer> list = new ArrayList<>(); // 结果列表
        for(int i = 1; i <= nums.length; i++) {
            if(!set.contains(i)) list.add(i); // 如果数字未出现，加入结果列表
        }
        return list;
    }

    /**
     * 使用哈希表查找消失的数字。
     * 该方法通过哈希表记录每个数字出现的次数，未出现的数字即为消失的数字。
     * @param nums 输入数组
     * @return 消失的数字列表
     */
    public List<Integer> findDisaMap(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>(); // 哈希表
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1); // 统计每个数字出现的次数
        }
        List<Integer> list = new ArrayList<>(); // 结果列表
        for(int i = 1; i < nums.length; i++) {
            if(!map.containsKey(i)) list.add(i); // 如果数字未出现，加入结果列表
        }
        return list;
    }

    /**
     * 使用哈希表查找消失的数字。
     * 该方法通过哈希表记录每个数字出现的次数，未出现的数字即为消失的数字。
     * @param nums 输入数组
     * @return 消失的数字列表
     */
    public List<Integer> findDisaNum(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>(); // 哈希表
        List<Integer> list = new ArrayList<>(); // 结果列表
        for(int i = 1; i <= nums.length; i++) {
            map.put(i, 0); // 初始化哈希表，所有数字初始出现次数为0
        }
        for(int num : nums) {
            map.put(num, map.get(num) + 1); // 统计每个数字出现的次数
        }
        for(int key : map.keySet()) {
            if(map.get(key) == 0) list.add(key); // 如果数字未出现，加入结果列表
        }
        return list;
    }

    /**
     * 使用原地交换查找消失的数字。
     * 该方法通过原地交换将数字放到正确的位置，未在正确位置的数字即为消失的数字。
     * @param nums 输入数组
     * @return 消失的数字列表
     */
    public List<Integer> findDisa(int[] nums) {
        int len = nums.length;
        int lef = 0;
        while(lef < len) {
            if(nums[lef] == (lef + 1)) {
                lef++;
                continue; // 如果当前位置的数字正确，继续下一个
            }
            int rig = nums[lef] - 1;
            if(nums[lef] == nums[rig]) {
                lef++;
                continue; // 如果当前位置的数字已经在正确位置，继续下一个
            }
            swap(nums, lef, rig); // 交换数字到正确位置
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < len; i++) {
            if(nums[i] != (i + 1)) list.add(i + 1); // 如果位置不正确，加入结果列表
        }
        return list;
    }

    /**
     * 交换数组中的两个元素。
     * @param nums 输入数组
     * @param left 左索引
     * @param right 右索引
     */
    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    /**
     * 主方法，处理输入并输出结果。
     * 从标准输入读取数组，并输出多种方法的结果。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        findDisappearedNumbers fdn = new findDisappearedNumbers();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()) {
            String[] s = sc.nextLine().split(",");
            int[] nums = new int[s.length];
            for(int i = 0; i < s.length; i++) {
                nums[i] = Integer.parseInt(s[i]); // 解析输入数组
            }
            System.out.println("set:" + fdn.findDisaSet(nums)); // 输出哈希集合方法的结果
            System.out.println("hash2: " + fdn.findDisaMap(nums)); // 输出哈希表方法的结果
            System.out.println("hash1:" + fdn.findDisaNum(nums)); // 输出哈希表方法的结果
            System.out.println("origin: " + fdn.findDisa(nums)); // 输出原地交换方法的结果
        }
        sc.close();
    }
}
